Phân tích cụm phân cấp là gì? Nghiên cứu khoa học liên quan

Định nghĩa phân tích cụm phân cấp

Phân tích cụm phân cấp (hierarchical clustering) là một phương pháp học máy không giám sát, được sử dụng để nhóm các đối tượng dữ liệu thành các cụm (clusters) dựa trên mức độ tương đồng của chúng. Mục tiêu là tạo ra một cấu trúc phân cấp thể hiện mối quan hệ giữa các cụm, thường được biểu diễn dưới dạng biểu đồ cây (dendrogram).

Trong kỹ thuật này, mỗi điểm dữ liệu ban đầu được xem là một cụm riêng biệt. Sau đó, các cụm được kết hợp từng bước dựa trên khoảng cách giữa chúng, cho đến khi tất cả dữ liệu hợp nhất thành một cụm duy nhất (trong phương pháp kết hợp), hoặc tách dần từ một cụm tổng thể thành các cụm nhỏ hơn (trong phương pháp phân rã).

Không giống như các thuật toán như K-means hoặc DBSCAN, phương pháp này không yêu cầu xác định trước số cụm. Điều này đặc biệt hữu ích trong các trường hợp cần khám phá dữ liệu hoặc phân tích mối quan hệ phân tầng trong hệ thống.

Phân biệt với các phương pháp phân cụm khác

Phân cụm phân cấp khác biệt với các phương pháp phân cụm “phẳng” như K-means hoặc phương pháp dựa trên mật độ như DBSCAN. Các phương pháp phẳng yêu cầu chỉ định trước số cụm hoặc ngưỡng mật độ, trong khi phân cụm phân cấp hoạt động dựa trên khoảng cách và xây dựng cấu trúc phân tầng, cho phép cắt cụm linh hoạt tại nhiều cấp độ khác nhau.

Bảng so sánh dưới đây minh họa sự khác biệt giữa một số thuật toán phổ biến:

Thuật toán	Yêu cầu tham số	Khả năng mở rộng	Ưu điểm	Nhược điểm
Hierarchical	Không cần số cụm	Vừa	Dendrogram chi tiết	Chi phí tính toán cao
K-means	Cần số cụm $k$	Cao	Hiệu quả với dữ liệu lớn	Phụ thuộc khởi tạo
DBSCAN	$\varepsilon$, minPts	Trung bình	Phát hiện cụm không cầu	Khó tối ưu tham số

Scikit-learn – Hierarchical Clustering

Phân loại phân cụm phân cấp

Có hai loại chính trong phân cụm phân cấp: phương pháp kết hợp (agglomerative) và phương pháp phân rã (divisive). Phương pháp kết hợp là phổ biến hơn trong thực tiễn và được hỗ trợ rộng rãi trong các thư viện phân tích dữ liệu.

Trong phân cụm kết hợp, thuật toán bắt đầu với mỗi điểm là một cụm riêng. Ở mỗi bước, hai cụm gần nhất được hợp nhất cho đến khi chỉ còn một cụm duy nhất. Đây là quá trình từ dưới lên (bottom-up). Ngược lại, trong phân cụm phân rã, thuật toán bắt đầu với một cụm bao gồm toàn bộ dữ liệu và tách dần từng cụm nhỏ hơn, đi theo hướng từ trên xuống (top-down).

So sánh hai phương pháp:

• Agglomerative: Thường dùng, hiệu quả tốt, dễ trực quan hóa.
• Divisive: Khó triển khai, ít được dùng do tốn tài nguyên tính toán.

Trong các thư viện phổ biến như scikit-learn hoặc scipy, phương pháp kết hợp là mặc định khi triển khai phân tích cụm phân cấp.

Đo lường khoảng cách giữa cụm

Để thực hiện phân cụm phân cấp, điều quan trọng là định nghĩa cách đo khoảng cách giữa các cụm. Khoảng cách này không chỉ xác định sự tương đồng giữa hai điểm mà còn giữa hai tập hợp điểm. Có nhiều chiến lược khác nhau để làm việc này, mỗi cách sẽ dẫn đến cấu trúc cụm khác nhau.

• Liên kết đơn (single linkage): Khoảng cách giữa hai cụm là khoảng cách nhỏ nhất giữa các điểm thuộc hai cụm đó.
• Liên kết hoàn chỉnh (complete linkage): Khoảng cách lớn nhất giữa các điểm của hai cụm.
• Liên kết trung bình (average linkage): Trung bình khoảng cách giữa mọi cặp điểm thuộc hai cụm.
• Liên kết trung tâm (centroid linkage): Khoảng cách giữa trung tâm (centroid) của hai cụm.

Công thức khoảng cách phổ biến nhất là khoảng cách Euclidean:

$d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$

Tùy vào mục tiêu phân tích và bản chất của dữ liệu, lựa chọn chiến lược đo khoảng cách sẽ ảnh hưởng đáng kể đến kết quả cụm cuối cùng. Trong các tập dữ liệu có hình dạng cụm kéo dài hoặc không đồng nhất, liên kết đơn có thể gây ra hiệu ứng "chuỗi" (chaining effect), còn liên kết hoàn chỉnh lại có xu hướng tạo các cụm chặt hơn.

Dendrogram và cắt cụm

Kết quả của phân tích cụm phân cấp thường được biểu diễn dưới dạng biểu đồ cây gọi là dendrogram. Đây là công cụ trực quan mạnh mẽ giúp hiển thị cấu trúc phân tầng của dữ liệu. Trục tung thể hiện khoảng cách hoặc độ tương đồng giữa các cụm, trong khi các nhánh cây cho biết trình tự hợp nhất hoặc phân tách cụm.

Việc xác định số lượng cụm trong dendrogram không cố định mà phụ thuộc vào việc cắt cây tại một ngưỡng độ cao nhất định. Việc chọn ngưỡng cắt phù hợp giúp chia cây thành các nhánh tương ứng với các cụm dữ liệu có ý nghĩa. Một cách phổ biến là tìm “khoảng nhảy” lớn nhất giữa các mức liên kết để quyết định vị trí cắt.

Ví dụ, nếu đoạn dài nhất không bị phân chia trong dendrogram nằm ở khoảng giá trị 7 trên trục khoảng cách, thì có thể chọn ngưỡng cắt tại giá trị này để chia tập dữ liệu thành các cụm ổn định. Trong thực tế, dendrogram được sử dụng cùng với các kỹ thuật đánh giá như chỉ số Silhouette hoặc Gap Statistic để xác thực cấu trúc cụm.

Ưu điểm và nhược điểm

Phân tích cụm phân cấp có nhiều ưu điểm khiến nó trở thành lựa chọn quan trọng trong các bài toán khám phá dữ liệu, đặc biệt là khi không biết trước số cụm hoặc cần tìm hiểu cấu trúc phân tầng của dữ liệu.

• Không yêu cầu xác định số cụm trước khi phân tích.
• Cho phép khám phá phân tầng tự nhiên trong dữ liệu.
• Hiển thị kết quả trực quan dễ hiểu qua dendrogram.
• Hoạt động tốt trên tập dữ liệu nhỏ và trung bình.

Tuy nhiên, phương pháp này cũng có một số hạn chế nghiêm trọng:

• Chi phí tính toán cao, đặc biệt với dữ liệu lớn do phải tính toàn bộ ma trận khoảng cách và duyệt cây.
• Nhạy cảm với nhiễu và điểm ngoại lai.
• Không thể sửa đổi hoặc đảo ngược quyết định phân cụm sau khi đã gộp.

Vì vậy, trong trường hợp xử lý hàng triệu mẫu, người ta thường dùng phương pháp phân cụm phẳng hoặc triển khai các biến thể gần đúng để tiết kiệm tài nguyên tính toán.

Ứng dụng trong thực tế

Phân tích cụm phân cấp được ứng dụng rộng rãi trong nhiều lĩnh vực nghiên cứu và công nghiệp, nơi cần phân nhóm các đối tượng có quan hệ phân tầng hoặc khi dữ liệu không có cấu trúc cụm rõ ràng.

• Phân tích gen: Gom nhóm các gen hoặc mẫu sinh học dựa trên biểu hiện gene (microarray data), giúp xác định các nhóm chức năng sinh học.
• Tiếp thị và kinh doanh: Phân khúc khách hàng dựa trên hành vi, chi tiêu, hoặc tương tác với sản phẩm.
• Phân tích tài liệu: Nhóm các tài liệu hoặc trang web theo nội dung hoặc chủ đề, ứng dụng trong máy tìm kiếm và phân loại văn bản.
• Chẩn đoán y học: Phân loại bệnh nhân hoặc mẫu bệnh lý dựa trên các chỉ số lâm sàng hoặc hình ảnh.

Trong các nghiên cứu khảo sát xã hội học hoặc tâm lý học, hierarchical clustering thường được dùng để phát hiện các nhóm thái độ, hành vi, hoặc các kiểu mẫu phản ứng trong bảng câu hỏi.

Triển khai thuật toán bằng phần mềm

Phân tích cụm phân cấp được hỗ trợ bởi nhiều thư viện mã nguồn mở và phần mềm thống kê. Tùy theo ngôn ngữ và mục đích sử dụng, người dùng có thể lựa chọn các công cụ phù hợp:

• Python: Thư viện scikit-learn cung cấp thuật toán Agglomerative Clustering, cùng hàm plot_dendrogram để trực quan hóa.
• R: Các hàm hclust() và dendrogram() trong gói stats hỗ trợ đầy đủ phân tích phân cấp.
• MATLAB: Cung cấp hàm linkage và dendrogram cho xử lý dữ liệu số lượng lớn.

Quy trình triển khai điển hình gồm:

1. Chuẩn hóa dữ liệu để đảm bảo các đặc trưng có cùng tỷ lệ ảnh hưởng.
2. Tính toán ma trận khoảng cách (Euclidean, cosine, hoặc Mahalanobis).
3. Áp dụng thuật toán liên kết cụm (single, complete, average, centroid).
4. Vẽ dendrogram và lựa chọn ngưỡng cắt cụm.
5. Đánh giá cụm bằng chỉ số như Silhouette Score.

Các biến thể nâng cao như Ward linkage (giảm phương sai nội cụm) cũng được hỗ trợ trong scikit-learn và được khuyến khích khi xử lý dữ liệu số học có tính tuyến tính cao.

Tài liệu tham khảo

1. Jain, A. K., & Dubes, R. C. (1988). Algorithms for Clustering Data. Prentice-Hall.
2. Müllner, D. (2011). Modern hierarchical, agglomerative clustering algorithms. arXiv:1109.2378.
3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning. Springer.
4. Scikit-learn – Hierarchical Clustering
5. Nature Reviews Genetics – Clustering and visualization of gene expression data
6. Sneath, P. H. A., & Sokal, R. R. (1973). Numerical Taxonomy. W.H. Freeman.